//自己
class Solution {
public:
int search(vector<int>& nums, int target) {
    int left=0, right=nums.size()-1, mid=0;
    while (left <= right)
        {
            mid = (left+right) / 2;//left + right 有溢出风险
            mid = left + (right-left) / 2;//防溢出
            if (nums[mid] < target) left = mid + 1;
            else if (nums[mid] > target)    right = mid - 1;
            else    return mid; // ==
        }
    //left > right跳出, 没找到
    return -1;
}
};
//时间复杂度: O(logN)
//空间: O(1)


//答案
class Solution {
public:
int search(vector<int>& nums, int target) {
    int left=0, right=nums.size()-1, mid=0;
    while (left <= right)
        {
            mid = (left+right) / 2;
            if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid - 1;
            else 
                return mid; // ==
        }
    //left > right跳出, 没找到
    return -1;
}
};
//时间复杂度: O(logN)
//空间: O(1)